3D Coding TAT - Non-Linear (Curved) Landscapes
Instead of simply using "Linear Interpolation" (drawing a straight line between 2 points) when drawing each map polygon which gives a sharp looking landscape, we could use Splines or Bezier-Curves instead. But they require far more work than a simple straight line because the slope between two pixels can change by varying amounts so that clipping them inside the screen boundary edges can be more difficult and SLOWER. I haven't looked too much into these kinds of curves as the few descriptions and source I have seen are too bulky and slow for a fast 3d terrain. They tend to leave gaps between two points on a curve which must be connected with a straight line also they work in a random-access like way (or more correctly a binary tree way) so the address of these pixels on the curve must be recalculated. What we actually want to do is to move from pixel to neighbouring pixel using the least number of computations as possible for the other axis. This means that we want to increment along one axis a pixel at a time and calculate the other axis coordinates from there.
Bezier curves seem to use a stack based sub-division method to create a number of points on the desired curve. After a number of these sub-divisions short lines are drawn between them to give the appearance of a continuous curve.
1: Circles
The best known curve is a circle or arc of a circle. This has the properties of having a fixed radius from one point (the origin) and having a constant change of slope from one pixel to the next. Circles can be drawn in two ways. Either using the parametric equation:
x = radius * COS (angle)
y = radius * SIN (angle)
which can also be used for ellipses, like this:
x = horz_radius * COS (angle)
y = vert_radius * SIN (angle)
But both these equations give a random placement of pixels around the circumference of the circle or ellipse. This means that recalculation of each pixel is required. Also gaps or pixel overdraw can occur with this method.
A much better method is to use R^2 = X^2 + Y^2 equation for a circle. This may look much slower than the 2 multiplies used for the parametric method, but it can be performed using a SUBtract and 2 ADDitions. The advantage of this method is that we can calculate one axis value given the other. This means that we can easily scan-convert it and draw horizontal lines for a filled circle. First rearrange it to give the value of X for any given Y line.
X^2 = R^2 - Y^2
We take the square-root (SQRT) of X^2 to give X, now we have:
X = SQRT(R*R + Y*Y)
In pseudo-code it would be:
R = radius of the circle
for Y = 0 to R step 1
X = sqrt(R*R-Y*Y)
line (-X,+Y) to (+X,+Y)
line (-X,-Y) to (+X,+Y)
next Y
As the Y variable only changes by 1 and R*R doesn't change inside the loop a few speed ups can be made. I will use the names XX to represent X^2 and RR for R^2 and so on. We also know that the first value of X will be equal to R because X=sqrt(R*R-Y*Y) and as Y=0 this means X=SQRT(R*R-0*0). Also as Y increases X will decrease. Looking at sequential squares and square-roots we can work out that each square number changes by 2 * n + 1 where n is the current SQRT. (If you don't understand where the 2n+1 comes from write down the first 10 square numbers and find the difference between each one, it should increase by 2 for each number.)
number square number difference
-------- --------------- ------------
0 0
1 1 1
2 4 3
3 9 5
4 16 7
5 25 9
6 36 11
7 49 13
8 64 15
9 81 17
We can use this 2n+1 fact for finding the next and previous square numbers without having to do a multiply or a SQRT within the main loop.
Here is a working QBASIC listing to demonstrate:
SCREEN 13
XC = 160 : YC = 100
R = 90
RR = R * R
X = R
XX = RR
YY = 0 * 0
FOR Y = 0 TO R STEP 1
LINE (XC-X, YC-Y)-(XC+X, YC-Y)
LINE (XC-X, YC+Y)-(XC+X, YC+Y)
YY = YY + (Y + Y + 1)
LL = RR - YY
WHILE XX > LL
X = X - 1
XX = XX - (X + X + 1)
WEND
NEXT Y
The above can be optimized much further, it is left to the reader as an exercise (heh heh). A clue is to only 45 degrees of a circle and using (Y,X) coordinates to plot the other 45 degrees.
2: Sub-division & Mid-points
I have already said in the patchwork section about taking a flat polygon and sub-dividing it down into a number of smaller polygons so that a greater range of shading can be drawn. The quickest sub-division is the mid-point. This is just the average coordinates of the two end vertices. This average must be performed on each coordinate axis, so for 2d sub-division 2 of these averages must be performed.
e.g.
x1 + x2 y1 + y2
xc = --------- yc = ---------
2 2
This gives the 'mid-point' of the two end points (x1,y1) and (x2,y2) as coordinates (xc,yc). Even though we have sub-divided these coordinates it is still a LINEAR-INTERPOLATION between them. If you draw a staight from (x1,y1) to (x2,y2) then (xc,yc) would also be on the line exactly at the centre (the mid-point). This isn't too helpful for drawing curves is it? But this type of averaging is used in Bezier curves (where a number of average are used to produce a new point) and could possibly be used in line drawing (the line is split into 2 halves using the centre point which is plotted and then these are split into 2 and so on...)
3: Fractional Curves
There is one thing which you must know in order to draw curves, You MUST have 3 or more points to define a curve otherwise it is simply be a straight-line (2 points) or a single pixel (1 point). Given two end points of a map cell's edge it does appear that we can not draw a curve unless we define a 3rd vertex which means more storage and more processing for rotation and projection.
But why don't we use a neighbouring cell vertex to be the 3rd point? It would be nice to shape the curve using the neighbouring cell vertices from BOTH sides rather than just one. So now we have 4 vertex points (which is another favourite number for programmers). Even Bezier curve method seems to use 4 control points to define the curve, as 3 is not a quick number to divide by.
V vertices
e.g. ..o.. --------------
.. .. 1 (Ax,Ay)
B . . C 2 (Bx,By)
o-----*-----o 3 (Cx,Cy)
/ M \ 4 (Dx,Dy)
/ \
/ \
/ \
/ \
o o
A D
In the above diagram we have 4 vertex points A,B,C and D and we want to draw the B..C line section. We know that it must be shaped by the neighbouring sections A..B and C..D We can find the mid-point M coordinates of section B..C by doing this:
Bx + Cx By + Cy
Mx = --------- My = ---------
2 2
But the point (Mx,My) lies directly on the B..C line section. What we want to do is push it up away from the mid-point M and towards point V. We can see that both the neighbouring line sections A..B and C..D are pointing upwards, this means that By > Ay and that Cy > Dy. We can simply use the length of each one and adjust the mid-point M by some fraction of the two. The easiest is a division by a power of 2, so let's use 8.
By + Cy By - Ay Cy - Dy
My = --------- + --------- + ---------
2 8 8
The same could also be done for the X coordinate of point M, like this (but using only 1 variable axis means we can step along one axis 1 pixel at a time).
Bx + Cx Bx - Ax Cx - Dx
Mx = --------- + --------- + ---------
2 8 8
This fractional method (moving the mid-point by a scaled down amount of the surrounding map cells) can be applied in both directions over the 2d map array, so that a map cell is shaped from north-to-south and from east-to-west this would give a cushion affect where the cell is shaped from it's four surrounding neighbour which is what we want. This technique (with a little care) can be used repeatedly to sub-divide again and again, using the M point with the (Mx,My) coordinates to be an end vertex. I have coded a few little test programs in QBASIC to check out the algorithm and it does work. It is best to use map cell lengths which of a power of 2 (128, 256, 1024 etc.). Use a buffer of the same length and sub-divide the mid-point of the two ends and then the mid-points between these 2 halves and so on...
o--------------------------------------------------------------o
o------------------------------1-------------------------------o pass 1
o--------------2---------------o-----------------3-------------o pass 2
o------4-------o-------5-------o-------6---------o-------7-----o pass 3
4: Parabolic Curves
Another way to draw curves quickly which I have recently figured out from a scrap of info which hinted at this method but gave absolutely NO source code or formula. ("...parabolic approximation...using 2 Adds per pixel...") After a spark of inspiration and head scratching I worked this method out, I'm not sure if this is how the person who hinted at this technique found it or whether this is what they meant but here goes ....
A parabolic curve is like the trajectory of an object fired out of a cannon and affected by gravity. (I'm not even gonna think about drawing an ASCII diagram.) We can easily perform a "fake-G" function by using two variables one for speed and one for the change in speed. In essence we do a cheap acceleration or deceleration of one axis coordinate while we simply step the other by a set amount. A parabola can be drawn with the following formula:
e.g.
x^2
y = ----
4a
The above calculation could be done within the loop for every X coordinate, but it can be done using the hinted at 2 ADDs. Here is a QBASIC example:
screen 12
a = 100
i = 1 / (2*a)
s = 0
y = 0
for x = 0 to 100
pset (x,y)
s = s + i
y = y + s
next x
Yep, it's THAT easy. The only complication is the fraction part of i, s and y need to be kept, so either floating-point or fixed-point numbers must be used.
DANGER, DANGER WILL ROBINSON
There are two minor problems with the 2 ADD method.
1. Acculative errors will occur for many loop interations
2. There is a divide to calculate the 1/(2*a) term
Point 1: Don't do very long lines or recalculate after a number of times. You could possibly round the increment either up or down this may help a little.
Point 2: You can build a small table of 1/(2*a) for every value of a you wish and look-up the value instead of doing a divide everytime. You could also do the rounding when the table is generated so gaining a few more CLK cycles. Remember the table MUST be either in a floating-point or a fixed-point format to describe the fraction!